#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"

using namespace std;
/*HJJ QQ479287006
 *
 * */

//递归合并
ListNode *merge(ListNode *l1, ListNode *l2) {
    //递归到底的情况
    if (l1 == nullptr) return l2;
    if (l2 == nullptr) return l1;
    //分情况递归实现
    if (l1->val <= l2->val) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l2->next, l1);
        return l2;
    }
}

//
ListNode *mergeSort(ListNode *head) {
    if (!head || !head->next)
        return head;

    ListNode *first = head;
    ListNode *second = head;
    ListNode *breakN = head;
    //注意条件
    while (second && second->next) {
        breakN = first;//这个也有问题 注意置空
        first = first->next;

        second = second->next->next;
    }
    breakN->next = nullptr;

    ListNode *l = mergeSort(head);
    ListNode *r = mergeSort(first);

    return merge(l, r);
}


ListNode *sortList(ListNode *head) {
    return mergeSort(head);
}








//ListNode* merge(ListNode* l1, ListNode* l2) {
//    //递归到底的情况
//    if (l1 == nullptr) return l2;
//    if (l2 == nullptr) return l1;
//
//    // 1 2 3
//    // 4 5 6
//    if (l1->val>l2->val){
//        l2->next=merge(l1, l2->next);
//        return l2;
//    } else{
//        l1->next=merge(l1->next, l2);
//        return l1;
//    }
//
//
//
//}















